<?php
// https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247484500&idx=1&sn=83f4df1253f597898b2f74ea9dca9fd9&chksm=9bd7fa5caca0734ad182ba67651882647a71264938eaa98e49c5ff43369b807a094ad16efcd4&scene=178&cur_album_id=1318896187793260544#rd

class LFUCache {
    // key 到 val 的映射
    private $keyToVal = array();

    // key 到 freq 的映射
    private $keyToFreq = array();

    // freq 到 key 列表的映射
    private $freqToKeys = array();

    // 记录最小的频次
    private $minFreq = 0;

    // 记录 LFU 缓存的最大容量
    private $cap;

    /**
     * @param Integer $capacity
     */
    function __construct($capacity) {
        $this->cap = $capacity;
    }

    public function get($key) {
        if (! isset($this->keyToVal[$key])) {
            return -1;
        }

        // 增加 key 对应的 freq
        $this->increaseFreq($key);

        return $this->keyToVal[$key];
    }

    public function put($key, $val) {
        if ($this->cap <= 0) return;

        // 若 key 已存在，修改对应的 val 即可
        if (isset($this->keyToVal[$key])) {
            $this->keyToVal[$key] = $val;

            // key 对应的 freq 加一
            $this->increaseFreq($key);

            return;
        }

        // key 不存在，需要插入

        // 容量已满的话需要淘汰一个 freq 最小的 key
        if ($this->cap <= count($this->keyToVal)) {
            $this->removeMinFreqKey();
        }

        $addNode = new Node($key, $val);

        // 插入 KV 表
        $this->keyToVal[$key] = $val;

        // 插入 KF 表，对应的 freq 为 1
        $this->keyToFreq[$key] = 1;

        // 初始化 FK 表
        if (! isset($this->freqToKeys[1])) {
            $this->freqToKeys[1] = new LinkedList();
        }
        $this->freqToKeys[1]->addLast($addNode);

        // 插入新 key 后最小的 freq 肯定是 1
        $this->minFreq = 1;
    }

    // 移除最少访问key
    public function removeMinFreqKey()
    {
        // freq 最小的 key 列表
        $keyList = $this->freqToKeys[$this->minFreq];

        // 更新 FK 表，其中最先被插入的那个 key 就是该被淘汰的 key
        $deletedNode = $keyList->removeFirst();

        if ($keyList->size() == 0) {
            unset($this->freqToKeys[$this->minFreq]);
            // 问：这里需要更新 minFreq 的值吗？
            // 其实这里没必要更新minFreq变量，因为你想想removeMinFreqKey这个函数是在什么时候调用？在put方法中插入新key时可能调用。而你回头看put的代码，插入新key时一定会把minFreq更新成 1，所以说即便这里minFreq变了，我们也不需要管它。
        }

        $deletedKey = $deletedNode->key;

        // 移除 KV 表
        unset($this->keyToVal[$deletedKey]);

        // 移除 KF 表
        unset($this->keyToFreq[$deletedKey]);
    }

    // 增加key的访问频率 +1
    public function increaseFreq($key)
    {
        $freq = $this->keyToFreq[$key];

        // 更新 KF 表
        $this->keyToFreq[$key] = $freq + 1;

        // 更新 FK 表
        // 将 key 从 freq 对应的列表中删除
        $keyList = $this->freqToKeys[$freq];
        $mvNode = $keyList->removeByKey($key);

        // 如果 freq 对应的列表空了，移除这个 freq
        if ($keyList->size() == 0) {
            unset($this->freqToKeys[$freq]);
            // 如果这个 freq 恰好是 minFreq，更新 minFreq
            if ($freq == $this->minFreq) {
                $this->minFreq++;
            }
        }

        // 将 key 加入 freq + 1 对应的列表中
        if (! isset($this->freqToKeys[$freq + 1])) {
            $this->freqToKeys[$freq + 1] = new LinkedList();
        }
        $this->freqToKeys[$freq + 1]->addLast(new Node($key, $mvNode->val));
    }
}

class LinkedList
{
    // 头尾虚节点
    private  $head;
    private  $tail;

    // 链表元素数
    private $size;

    public function __construct()
    {
        $head = new Node(0, 0);
        $tail = new Node(0, 0);

        $this->head = $head;
        $this->tail = $tail;

        $this->head->next = $this->tail;
        $this->tail->prev = $this->head;
    }

    // 在链表尾部添加节点 x，时间 O(1)
    public function addLast(Node $x)
    {
        $x->prev = $this->tail->prev;

        $x->next = $this->tail;

        $this->tail->prev->next = $x;

        $this->tail->prev = $x;

        $this->size++;

        return $this;
    }

    // 删除链表中的 x 节点（x 一定存在）
    // 由于是双链表且给的是目标 Node 节点，时间 O(1)
    public function remove(Node $x)
    {
        $x->prev->next = $x->next;

        $x->next->prev = $x->prev;

        $this->size--;
    }

    // 删除链表中第一个节点，并返回该节点，时间 O(1)
    public function removeFirst()
    {
        if ($this->head->next == $this->tail) {
            return null;
        }

        $first = $this->head->next;

        $this->remove($first);

        return $first;
    }

    public function removeByKey($key)
    {
        if ($this->head->next == $this->tail) {
            return null;
        }

        $node = $this->head->next;
        while ($node) {
            if ($node->key == $key) {
                break;
            }
        }

        $this->remove($node);

        return $node;
    }

    // 返回链表长度，时间 O(1)
    public function size()
    {
        return $this->size;
    }
}

class Node {
    public $key;
    public $val;

    public $next;
    public $prev;

    public function __construct($k, $v)
    {
        $this->key = $k;
        $this->val = $v;
    }
}